package microsfot.java;

import java.util.Arrays;

import alogrithm.list.LinkList;
import alogrithm.list.LinkNode;

public class LinkListHasCommonNode {
	/**
	 * 思路
	 * 从a和b两个链表中找到值最大的节点，记其值MAX
	 * 声明一个数组int flag[MAX],初始标记为0
	 * 
	 * 遍历链表a，判断flag[ai]是否存在，存在即为1
	 * 
	 * 遍历链表b，判断flag[bi]是否为1，为1则表示相交
	 * @param a
	 * @param b
	 */
	public void hasCommonNode(LinkNode<Integer> a,LinkNode<Integer> b){
		int max=0;
		LinkNode<Integer> la=a;
		while(la!=null){
			if(la.data>max){
				max=la.data;
			}
			la=la.next;
		}
		
		LinkNode<Integer> lb=b;
		while(lb!=null){
			if(lb.data>max){
				max=lb.data;
			}
			lb=lb.next;
		}
		
		int flag[]=new int[max+1];
		for(int i=0;i<flag.length;i++){
			flag[i]=0;
		}
		
		LinkNode<Integer> lla=a;
		while(lla!=null){
			flag[lla.data]=1;
			lla=lla.next;
		}
		
		LinkNode<Integer> llb=b;
		while(llb!=null){
			if(flag[llb.data]==1){
				flag[llb.data]=2;
				System.out.println("链表相交，节点为"+llb.data);
			}
			llb=llb.next;
		}
		System.out.println(Arrays.toString(flag));
	}
	
	public static void main(String[] args) {
		LinkListHasCommonNode hs=new LinkListHasCommonNode();
		LinkList<Integer> a=new LinkList<Integer>();
		a.add(1);
		a.add(2);
		a.add(3);
		a.add(20);
		
		LinkList<Integer> b=new LinkList<Integer>();
		b.add(4);a.add(1);a.add(9);a.add(10);a.add(20);
		
		hs.hasCommonNode(a.head, b.head);
	}
}
